로그 기반 파일 시스템(LFS) 완벽 분석: 디스크의 한계를 넘어서

오늘은 운영체제 역사에서 매우 중요한 전환점이 되었던 로그 기반 파일 시스템 (Log-structured File System, LFS) 에 대해 깊이 있게 다뤄보려고 합니다. 1990년대 초 Berkeley의 John Ousterhout 교수와 Mendel Rosenblum이 제안한 이 파일 시스템은 당시 하드웨어의 발전 흐름을 정확히 꿰뚫어 보고, 기존 파일 시스템(FFS 등)이 가진 비효율성을 극복하기 위해 등장했습니다.

비록 현대의 범용 리눅스에서 LFS를 메인으로 쓰는 경우는 드물지만, 그 사상(Copy-on-Write, Snapshot 등)은 ZFS, Btrfs, 그리고 우리가 매일 쓰는 낸드 플래시 SSD의 FTL(Flash Translation Layer)에 깊숙이 스며들어 있습니다.

이 글 하나로 LFS의 탄생 배경부터 설계 원리, 그리고 가장 골치 아픈 문제였던 가비지 컬렉션까지 완벽하게 정리해 보겠습니다.

1. 탄생 배경: 하드웨어의 변화를 읽다

모든 기술은 시대의 요구에 따라 탄생합니다. 1990년대 초, 시스템 연구자들은 두 가지 중요한 하드웨어 트렌드를 목격했습니다.

(1) 메모리 용량의 급격한 증가

시스템 메모리가 점점 커지면서, 디스크에 있는 데이터의 많은 부분을 메모리에 캐시(Cache)할 수 있게 되었습니다. 이는 '읽기(Read)' 성능이 파일 시스템 성능에 미치는 영향이 줄어든다는 것 을 의미합니다. 캐시에서 읽으면 되니까요. 결과적으로 디스크 I/O에서 '쓰기(Write)' 성능 이 전체 시스템 성능을 좌우하는 병목이 되기 시작했습니다.

(2) 임의 I/O와 순차 I/O의 성능 격차 확대

디스크의 전송 대역폭(Bandwidth)은 매년 비약적으로 발전했지만, 디스크 헤드를 움직이는 탐색 시간(Seek Time)과 회전 지연(Rotational Latency) 비용은 물리적 한계로 인해 아주 천천히 개선되었습니다. 즉, 디스크 여기저기를 왔다 갔다 하는 임의 쓰기(Random Write) 는 점점 더 비효율적인 작업이 되었고, 순차 쓰기(Sequential Write) 와의 성능 격차는 더욱 벌어졌습니다.

기존 파일 시스템(FFS)의 문제점

기존의 유닉스 파일 시스템(FFS)은 작은 파일을 생성할 때 많은 양의 임의 쓰기를 발생시켰습니다. 예를 들어, 4KB짜리 파일 하나를 만들려면 다음과 같은 작업이 필요했습니다.

새로운 아이노드(Inode) 쓰기
아이노드 비트맵 갱신
디렉터리 데이터 블록 갱신
디렉터리 아이노드 갱신
파일 데이터 블록 쓰기
데이터 비트맵 갱신

FFS는 이를 같은 블록 그룹에 배치하려 노력했지만, 근본적으로 여러 번의 짧은 탐색과 회전 지연을 피할 수 없었습니다. RAID 환경(특히 RAID-4, 5)에서는 작은 쓰기(Small Write)가 전체 패리티 갱신을 유발해 성능 저하가 더 심각했습니다.

그렇다면, 모든 쓰기 작업을 순차적으로 만들 수 없을까? 이것이 LFS의 출발점입니다.

2. 핵심 아이디어: 모든 것을 로그로 쓴다

LFS의 핵심은 간단하지만 강력합니다. 디스크에 쓰는 모든 변경 사항(데이터 블록, 메타데이터 등)을 메모리에 모았다가, 한 번에 디스크의 가장 끝부분에 순차적으로(Log처럼) 기록하는 것 입니다.

쓰기 버퍼링(Write Buffering)과 세그먼트(Segment)

LFS는 디스크에 바로 쓰지 않습니다. 갱신된 내용(데이터 블록, 아이노드 등)을 메모리 상의 세그먼트(Segment) 라는 거대한 버퍼에 차곡차곡 쌓습니다. 세그먼트가 가득 차면, 이 거대한 덩어리를 디스크의 빈 공간에 한 번에 씁니다.

이렇게 하면 자잘한 임의 쓰기 요청들이 하나의 거대한 순차 쓰기로 변환됩니다. 디스크 헤드는 한 번만 움직이면 되고, 그 뒤로는 최대 대역폭으로 데이터를 쏟아부을 수 있게 되죠.

최적의 세그먼트 크기는?

그렇다면 버퍼(세그먼트)를 얼마나 크게 잡아야 효율적일까요? 여기서 약간의 수학적 모델링이 필요합니다.

$T_{position}$ : 디스크 위치 잡기 시간 (Seek + Rotation)
$R_{peak}$ : 디스크의 최대 전송 속도 (MB/s)
$D$ : 우리가 쓰려는 데이터의 양 (MB)

데이터 $D$ 를 쓰는 데 걸리는 총시간 $T_{write}$ 는 다음과 같습니다. $T_{write} = T_{position} + \frac{D}{R_{peak}}$

우리는 실제 유효 전송 속도( $R_{effective}$ )가 최대 전송 속도( $R_{peak}$ )의 일정 비율( $F$ , 예를 들어 0.9 즉 90%) 이상이 되기를 원합니다. $R_{effective} = \frac{D}{T_{write}} = F \times R_{peak}$

이 식들을 정리하면, 목표 효율 $F$ 를 달성하기 위해 필요한 데이터 크기 $D$ 를 구할 수 있습니다. $D = \frac{F}{1-F} \times R_{peak} \times T_{position}$

예를 들어, 위치 잡기 시간이 10ms( $0.01s$ ), 최대 전송 속도가 100MB/s인 디스크에서 효율 90%( $F=0.9$ )를 내려면: $D = \frac{0.9}{0.1} \times 100 \text{MB/s} \times 0.01 \text{s} = 9 \text{MB}$

즉, 적어도 9MB 정도는 모아서 한 번에 써야 디스크 성능의 90%를 뽑아낼 수 있다는 계산이 나옵니다. LFS는 이렇게 큰 단위(세그먼트)로 쓰기를 수행하여 디스크 효율을 극대화합니다.

3. 아이노드 관리: 움직이는 아이노드를 찾아라

여기서 LFS의 구조적 난제가 발생합니다.

기존 FFS: 아이노드는 디스크의 고정된 위치(배열)에 있습니다. 아이노드 번호만 알면 수학적 계산으로 바로 위치를 알 수 있습니다.
LFS: 데이터를 덮어쓰지 않고 새로운 위치에 로그처럼 씁니다. 아이노드가 갱신되면, 아이노드 역시 새로운 세그먼트 어딘가에 새로 기록됩니다. 즉, 아이노드의 위치가 계속 바뀝니다.

아이노드 번호만 가지고, 현재 디스크 어디에 그 아이노드가 있는지 어떻게 알 수 있을까요?

아이노드 맵 (Inode Map, imap)

LFS는 이 문제를 해결하기 위해 아이노드 맵(imap) 이라는 간접 계층(Indirection Layer)을 도입합니다.

역할: 아이노드 번호(k)를 입력받으면 디스크 주소(A)를 반환합니다.
구조: 아이노드 번호를 인덱스로 하는 단순한 배열 형태입니다. 각 항목은 4바이트 디스크 주소입니다.

하지만 imap도 데이터입니다. 디스크에 저장되어야 하죠. imap은 어디에 저장할까요? 고정된 위치에 두면 imap을 갱신할 때마다 임의 쓰기가 발생하여 LFS의 취지를 해칩니다.

그래서 LFS는 imap 자체도 로그에 기록 합니다. 데이터 블록을 쓰고, 아이노드를 쓰고, 그 뒤에 갱신된 imap 조각을 연속해서 써버립니다.

체크포인트 영역 (Checkpoint Region, CR)

문제가 꼬리에 꼬리를 뭅니다. imap도 디스크 여기저기에 흩어져서 기록됩니다. 그럼 흩어진 imap들은 어떻게 찾을까요?

이를 위해 LFS는 디스크의 고정된 위치(보통 0번 주소) 에 체크포인트 영역(CR) 을 둡니다.

CR의 역할: 전체 imap 블록들의 최신 디스크 주소를 가지고 있습니다.
동작: 시스템이 부팅되거나 파일을 읽으려 할 때, 가장 먼저 CR을 읽습니다. CR을 통해 imap의 위치를 알아내고, imap을 메모리에 캐시한 뒤, imap을 통해 실제 아이노드의 위치를 찾습니다.
갱신: CR은 자주 갱신하지 않고 주기적(예: 30초)으로 씁니다. 따라서 성능 오버헤드가 크지 않습니다.

4. 디렉터리 관리와 재귀 갱신 문제 해결

디렉터리 역시 파일의 일종입니다. '이름: 아이노드 번호'의 매핑 정보를 담고 있죠. LFS에서 파일을 생성하거나 수정할 때 디렉터리는 어떻게 처리될까요?

재귀 갱신 문제 (Recursive Update Problem)

만약 LFS가 imap 같은 간접 계층을 쓰지 않았다면 심각한 문제가 발생했을 겁니다.

/foo/bar 파일의 내용을 수정해서 디스크의 새로운 위치에 씁니다.
bar의 아이노드 위치가 바뀝니다.
부모 디렉터리 foo는 bar의 아이노드 위치를 가리켜야 하므로, foo의 데이터 블록도 수정되어야 합니다.
foo가 수정되어 새로운 위치에 쓰이면, foo의 아이노드 위치도 바뀝니다.
그럼 foo의 부모인 루트 디렉터리(/)도 수정되어야 합니다.
파일 하나 고쳤는데 루트까지 모든 상위 디렉터리를 다시 써야 합니다.

LFS의 우아한 해결책

LFS는 imap 덕분에 이 문제를 겪지 않습니다.

bar 파일이 수정되어 새로운 위치에 쓰이고, 새로운 아이노드가 생성됩니다.
imap에서 bar의 아이노드 번호가 가리키는 주소만 갱신합니다.
부모 디렉터리 foo는 bar의 아이노드 번호 만 가지고 있습니다. 번호는 바뀌지 않았으므로, foo 디렉터리의 내용은 변하지 않습니다.
따라서 재귀적인 갱신이 발생하지 않습니다.

LFS에서 디렉터리 내의 파일 생성 과정은 다음과 같이 요약됩니다.

데이터 블록 쓰기
새 아이노드 쓰기
디렉터리 데이터 블록(이름, 아이노드 번호) 쓰기
디렉터리 아이노드 쓰기
갱신된 imap 조각 쓰기

이 모든 것은 하나의 세그먼트 안에서 순차적으로 이루어집니다.

5. 가비지 컬렉션 (Garbage Collection): LFS의 숙명

LFS의 가장 큰 특징이자 단점은 구버전 데이터(Garbage) 가 남는다는 점입니다. 데이터를 덮어쓰지 않고 계속 새로운 곳에 쓰기 때문에, 디스크에는 예전 버전의 아이노드와 데이터 블록들이 남게 됩니다. 이를 정리해 주지 않으면 디스크는 금방 꽉 차게 될 것입니다.

이 죽은 블록들을 정리하고 공간을 확보하는 작업을 가비지 컬렉션(Garbage Collection, GC) 또는 클리닝(Cleaning) 이라고 합니다.

세그먼트 단위의 클리닝

LFS는 쓰기도 세그먼트 단위로 하지만, 청소도 세그먼트 단위로 합니다.

여러 개의 세그먼트( $M$ 개)를 읽어 들입니다.
그 안에서 살아있는(Live) 블록 만 골라냅니다.
살아있는 블록들을 모아 더 적은 수의 새로운 세그먼트( $N$ 개, $N < M$ )로 꽉 채워 씁니다.
기존의 $M$ 개 세그먼트 공간은 비워집니다(Free).

블록의 생사 확인: 세그먼트 요약 블록 (Segment Summary Block)

세그먼트 안에 있는 블록이 살아있는지 죽었는지 어떻게 알 수 있을까요? 이를 위해 LFS는 각 세그먼트의 앞부분에 세그먼트 요약 블록(SSB) 을 둡니다.

SSB는 각 데이터 블록에 대해 다음 정보를 저장합니다.

소속 파일의 아이노드 번호 ( $N$ )
파일 내의 오프셋 ( $T$ )

판별 로직은 다음과 같습니다.

디스크 주소 $A$ 에 있는 블록을 검사합니다.
SSB를 보고 이 블록이 파일 $N$ 의 $T$ 번째 블록임을 확인합니다.
현재 imap을 조회하여 파일 $N$ 의 아이노드를 찾습니다.
그 아이노드가 가리키는 $T$ 번째 블록의 주소를 확인합니다.
그 주소가 $A$ 와 일치하면 이 블록은 살아있는(Live) 것입니다. 일치하지 않으면 최신 버전이 다른 곳에 있다는 뜻이므로 죽은(Garbage) 블록입니다.

LFS는 효율성을 위해 파일에 '버전 번호'를 부여하여 imap 조회 과정을 단축하기도 합니다.

정책: 언제, 무엇을 청소할 것인가?

가비지 컬렉션은 오버헤드가 큽니다. 어떤 세그먼트를 청소해야 효율적일까요? Rosenblum과 Ousterhout은 Hot(핫) 세그먼트 와 Cold(콜드) 세그먼트 를 구분하는 정책을 제안했습니다.

Hot 세그먼트: 데이터가 빈번하게 변경되는 세그먼트.
- 전략: 천천히 청소합니다. 왜냐하면, 금방 데이터가 덮어씌워져서 알아서 가비지가 될 확률이 높기 때문입니다. 굳이 살아있는 블록을 복사하는 수고를 할 필요 없이, 블록들이 다 죽을 때까지 기다리는 게 낫습니다.
Cold 세그먼트: 내용이 거의 변하지 않는 세그먼트.
- 전략: 빨리 청소합니다. 몇 개의 죽은 블록이 생기면 바로 정리해서 공간을 확보하는 것이 유리합니다.

이 정책은 '쓰기 비용(Write Cost)'을 최소화하기 위한 고민의 결과였습니다.

6. 크래시 복구 (Crash Recovery)

LFS는 메모리에 버퍼링을 하기 때문에, 전원이 갑자기 꺼지면(Crash) 데이터 손실 위험이 있습니다. LFS는 이를 어떻게 처리할까요?

체크포인트 영역(CR)의 원자적 갱신

LFS는 CR을 갱신하다가 크래시가 나는 것을 방지하기 위해 두 개의 CR을 디스크 양 끝에 두고 교대로 사용합니다. CR을 쓸 때는 [타임스탬프(헤더) -> CR 내용 -> 타임스탬프(테일)] 순서로 씁니다. 만약 헤더와 테일의 타임스탬프가 다르면, 기록 도중 크래시가 난 것으로 간주하고 그 CR은 버립니다. 복구 시에는 둘 중 타임스탬프가 더 최신이면서 온전한 CR을 선택합니다.

롤 포워드 (Roll-Forward)

CR은 주기적(예: 30초)으로 기록되므로, 마지막 체크포인트 이후의 데이터는 잃어버릴 수 있습니다. 이를 복구하기 위해 LFS는 데이터베이스의 기법인 롤 포워드 를 사용합니다.

마지막으로 유효한 체크포인트에서 시작합니다.
그 체크포인트가 가리키는 마지막 세그먼트를 찾습니다.
세그먼트 안에 있는 '다음 세그먼트 포인터'를 따라가며 CR 이후에 기록된 세그먼트들이 있는지 확인합니다.
유효한 세그먼트가 발견되면 그 안의 데이터와 메타데이터를 읽어 시스템 상태를 복구합니다.

이를 통해 마지막 체크포인트 이후 몇 초간의 데이터도 최대한 살려낼 수 있습니다.

7. 결론 및 요약

LFS는 디스크의 모든 쓰기를 순차적으로 만든다 는 급진적인 아이디어에서 출발했습니다.

LFS의 장점

쓰기 성능의 극대화: 임의 쓰기를 순차 쓰기로 변환하여 디스크 대역폭을 100% 가까이 활용합니다.
빠른 복구: fsck처럼 디스크 전체를 스캔할 필요 없이, 마지막 로그 끝부분만 확인하면 됩니다.

LFS의 단점

가비지 컬렉션 오버헤드: 디스크가 꽉 차거나 단편화가 심해지면, 클리닝 작업이 시스템 성능을 잡아먹습니다. 이는 LFS가 널리 상용화되는 데 걸림돌이 되었습니다.

현대적 유산

비록 순수 LFS는 메인스트림에서 물러났지만, 그 유산은 화려합니다.

WAFL (Write Anywhere File Layout): NetApp의 파일 시스템으로, LFS의 아이디어를 받아들여 스냅샷 기능을 구현하고 가비지 컬렉션 문제를 훌륭하게 비틀어 해결했습니다.
ZFS & Btrfs: 현대의 Copy-on-Write 파일 시스템들은 LFS의 사상을 계승하고 있습니다.
SSD FTL: 여러분이 쓰는 SSD 내부의 Flash Translation Layer 는 사실상 하드웨어 레벨에서 돌아가는 LFS입니다. 낸드 플래시는 덮어쓰기가 불가능하므로, LFS처럼 빈 공간에 쓰고 맵핑 테이블(imap 역할)을 관리하며 가비지 컬렉션을 수행합니다.

LFS를 공부하는 것은 단순히 과거의 파일 시스템 하나를 배우는 것이 아니라, 스토리지 시스템이 데이터를 관리하는 가장 기본적인 두 가지 방식(Update-in-place vs Log-structured) 중 하나를 마스터하는 것 입니다.

이 글이 여러분의 운영체제 공부에 큰 도움이 되었기를 바랍니다. 특히 개발자로서 데이터베이스나 스토리지 엔진의 내부를 이해할 때, 이 LFS의 원리는 두고두고 유용한 지식이 될 것입니다.

참고

OSTEP (Korean Version) 43 Log-Structured File System (LFS)

김재욱

woogiereal@gmail.com

github.com/woogieReal